package DymaticProgramming;

import java.util.Arrays;

public class Knapsack {
    public static void main(String[] args) {
        int N=3;//表示当前物品的数量
        int W=4;//表示背包的最大容量
        int[] wt={1,4,3};//wt[i]表示第i个物品的重量为多少
        int[] val={1500,2000,3000};//val[i]表示第i个物品的价值为多少
        System.out.println("最大价值:"+knapsack(N, W, wt, val));

    }

    /**
     * 01背包问题
     * 两种状态 背包的容量 可选择的物品
     * @param N  物品数量
     * @param W  背包容量
     * @param wt 物品占用的容量
     * @param val 物品的价值
     * @return    可放入的最大价值
     */
    public static int knapsack(int N,int W,int[] wt,int[] val){
        //定义一个dp数组，并都初始化为0
        int[][] dp =new int[N+1][W+1];
        //开始从物品列表里选择物品
        //为了符合人的习惯，从1开始，即拿出第一个物品
        for (int i = 1; i <= N; i++) {
            //拿出以后将其放入不同容量的背包中进行(试放入)，模拟的是一个试探的过程
            for (int w = 1; w <=W ; w++) {
                //每种背包容量都面临  放与不放的问题，放与不放的依据
                //是当前的物品的容量是否超过了当前背包的剩余容量
                //由于从1开始 需要-1再进行处理
                if(w-wt[i-1] <0){
                    //表明当前容量不可以容纳该物品
                    //那么当前背包的价值，应保持上一次放的价值
                    //动态规划在此体现,依赖上一次的结果
                    dp[i][w]=dp[i-1][w];
                }else {
                    //表明当前容量可以容纳该物品
                    //那么当前的价值应当和前一次进行比较，大者放入
                    //dp[i-1][w-wt[i-1]]+val[i-1]
                    //由于每次结果都会存在dp数组中，那么当放入当前物·品
                    //容量将减为w-wt[i-1]，这个容量的价值在dp数组中已有记录
                    //那么取出该价值加上第i-1个物品的价值，则为此次尝试访问的总价值
                    //那么此时在于上一次尝试的结果取比较，大者放入。
                    dp[i][w]=Math.max(dp[i-1][w-wt[i-1]]+val[i-1],dp[i-1][w]);
                }

            }

        }

        for (int[] value :
                dp) {
            System.out.println(Arrays.toString(value));
        };
        return dp[N][W];
    }
}
